// ====================== Kruskal 算法 ======================
class DisjointSetUnion
{
private:
    vector<int> f, rank;

public:
    DisjointSetUnion(size_t n)
    {
        rank.resize(n, 1);
        f.resize(n);
        for (size_t i = 0; i < n; i++)
        {
            f[i] = i;
        }
    }

    int find(int x)
    {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    bool unionSet(int x, int y)
    {
        int fx = find(x), fy = find(y);
        if (fx == fy)
        {
            return false;          // 两个节点构成连通关系
        }
        if (rank[fx] < rank[fy])
        {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
        return true;
    }

};

struct Edge
{
    int len, x, y;
    Edge(int len, int x, int y) :len(len), x(x), y(y) {}
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) 
    {
        auto dist = [&](int x, int y)->int
        {
            return abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1]);
        };
        
        int n = points.size();
        DisjointSetUnion dsu(n);
        vector<Edge> edges;
        for (size_t i = 0; i < n; i++)
        {
            for (size_t j = i + 1; j < n; j++)
            {
                edges.emplace_back(dist(i, j), i, j);
            }
        }
        sort(edges.begin(), edges.end(), [](Edge elem1, Edge elem2)->int
            {
                return elem1.len < elem2.len;
            });

        vector<Edge>::const_iterator iter = edges.begin();
        int ret = 0;
        for (; iter != edges.end(); iter++)
        {
            if (dsu.unionSet(iter->x, iter->y))
            {
                ret += iter->len;
            }
        }
        return ret;
    }
};